import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/8/6 10:00
 */
// 课程表II
    //https://leetcode.cn/problems/course-schedule-ii/
    // 需要返回所有可能的学习顺序
public class Solution210 {
    List<Integer> postorder = new ArrayList<>();
    boolean hasCycle = false;
    boolean[] visited, onPath;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            traverse(graph, i);
        }
        //有环图无法拓扑排序
        if (hasCycle) {
            return new int[]{};
        }
        // 逆后序遍历结果
        Collections.reverse(postorder);
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = postorder.get(i);
        }
        return res;
    }

    private void traverse(List<Integer>[] graph, int i) {
        if (onPath[i]) {
            hasCycle = true;
        }
        if (hasCycle || visited[i]) {
            return;
        }
        // 前序遍历位置
        onPath[i] = true;
        visited[i] = true;
        for (int t : graph[i]) {
            traverse(graph, t);
        }
        // 后序遍历位置
        postorder.add(i);
        onPath[i] = false;
    }

    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : prerequisites) {
            int from = edge[1], to = edge[0];
            graph[from].add(to);
        }
        return graph;
    }
}
